package com.love.labuladong.monotonicqueue;


/**
 * @Author : zh
 * @Description :
 * @Date : 2024-09-25 12:58
 */
public class LongestSubArrayAbsoluteLimit1438 {


    public static int MANX = 100001;

    // 窗口内最大值的更新结构(单调队列)
    public static int[] maxDeque = new int[MANX];

    // 窗口内最小值的更新结构（单调队列）
    public static int[] minDeque = new int[MANX];

    public static int maxh,maxt,minh,mint;

    public static int[] arr;

    public static int longestSubArray(int[] nums,int limit){
        maxh = maxt = minh = mint = 0;
        arr = nums;
        int n = arr.length;
        int ans = 0;
        for (int l = 0,r = 0; l < n; l++){
            // [l,N),r 永远是没进入窗口的、下一个数所在的位置
            while (r < n && ok(limit,nums[r])){
                push(r++);
            }
            // 从while出来的时候，[l,r)是l开头的子数组能向右延申的最大范围
            ans = Math.max(ans,r - l);
            pop(l);
        }
        return ans;
    }

    // 窗口要吐出l位置的数了
    private static void pop(int i) {
        if(maxh < maxt && maxDeque[maxh] == i){
            maxh++;
        }
        if(minh < mint && minDeque[minh] == i){
            minh++;
        }
    }

    private static void push(int i) {
        while (maxh < maxt && arr[maxDeque[maxt - 1]] <= arr[i]){
            maxt--;
        }
        maxDeque[maxt++] = i;
        while (minh < mint && arr[minDeque[mint - 1]] >= arr[i]){
            mint--;
        }
        minDeque[mint++] = i;
    }


    //判断如果加入数字number,窗口最大值 - 窗口最小值是否依然 <= limit
    // 依然 <= limit,返回true
    // 不再 <= limit,返回false
    public static boolean ok(int limit,int number){
        // max : 如果number进来，新窗口的最大值
        int max = maxh < maxt ? Math.max(arr[maxDeque[maxh]],number) : number;
        // min : 如果number进来，新窗口的最小值
        int min = minh < mint ? Math.min(arr[minDeque[minh]],number) : number;
        return max - min <= limit;
    }





}
